home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 2 / Amiga Tools 2.iso / tools / packer / ha0999beta / src / swdict.c < prev    next >
C/C++ Source or Header  |  1995-03-09  |  4KB  |  196 lines
  1. /***********************************************************************
  2.   This file is part of HA, a general purpose file archiver.
  3.   Copyright (C) 1995 Harri Hirvola
  4.  
  5.   This program is free software; you can redistribute it and/or modify
  6.   it under the terms of the GNU General Public License as published by
  7.   the Free Software Foundation; either version 2 of the License, or
  8.   (at your option) any later version.
  9.  
  10.   This program is distributed in the hope that it will be useful,
  11.   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.   GNU General Public License for more details.
  14.  
  15.   You should have received a copy of the GNU General Public License
  16.   along with this program; if not, write to the Free Software
  17.   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18. ************************************************************************
  19.     HA sliding window dictionary
  20. ***********************************************************************/
  21.  
  22. #include <stdlib.h>
  23. #include <stdio.h>
  24. #include "ha.h"
  25. #include "haio.h"
  26. #include "swdict.h"
  27. #include "error.h"
  28.  
  29. #define HSIZE    16384
  30. #define HSHIFT    3
  31. #define HASH(p) ((b[p]^((b[p+1]^(b[p+2]<<HSHIFT))<<HSHIFT))&(HSIZE-1))
  32. #define MAXCNT    1024    
  33.  
  34. U16B swd_bpos,swd_mlf;
  35. S16B swd_char;
  36. U16B cblen,binb;
  37. U16B bbf,bbl,inptr;
  38. U16B *ccnt=NULL,*ll=NULL,*cr=NULL,*best=NULL;
  39. unsigned char *b=NULL;
  40. U16B blen,iblen;
  41.  
  42. void swd_cleanup(void) {
  43.  
  44.     if (ccnt!=NULL) free(ccnt),ccnt=NULL;
  45.     if (ll!=NULL) free(ll),ll=NULL;
  46.     if (cr!=NULL) free(cr),cr=NULL;
  47.     if (b!=NULL) free(b),b=NULL;    
  48.     if (best!=NULL) free(best),best=NULL;    
  49. }
  50.  
  51. void swd_init(U16B maxl, U16B bufl) {
  52.     
  53.     register S16B i;
  54.     
  55.     iblen=maxl; 
  56.     cblen=bufl;
  57.     blen=cblen+iblen;
  58.     ll=malloc(blen*sizeof(*ll));
  59.     best=malloc(blen*sizeof(*best));
  60.     ccnt=malloc(HSIZE*sizeof(*ccnt));
  61.     cr=malloc(HSIZE*sizeof(*cr));
  62.     b=malloc((blen+iblen-1)*sizeof(*b));
  63.     if (ll==NULL || ccnt==NULL || cr==NULL || b==NULL) {
  64.     swd_cleanup();
  65.     error(1,ERR_MEM,"swd_init()");
  66.     }
  67.     for (i=0;i<HSIZE;++i) ccnt[i]=0; 
  68.     binb=bbf=bbl=inptr=0;
  69.     while (bbl<iblen) {
  70.     if ((i=getbyte())<0) break;
  71.     b[inptr++]=i;
  72.     bbl++;
  73.     }
  74.     swd_mlf=MINLEN-1;
  75. }
  76.  
  77. #ifndef PCASM
  78.  
  79. void swd_accept(void) {
  80.  
  81.     register S16B i,j;
  82.     
  83.     j=swd_mlf-2;
  84.     do {           /* Relies on non changed swd_mlf !!! */
  85.     if (binb==cblen) --ccnt[HASH(inptr)];
  86.     else ++binb;
  87.     i=HASH(bbf);
  88.     ll[bbf]=cr[i];
  89.     cr[i]=bbf;
  90.     best[bbf]=30000;
  91.     ccnt[i]++;
  92.     if (++bbf==blen) bbf=0;
  93.     if ((i=getbyte())<0) {
  94.         --bbl;
  95.         if(++inptr==blen) inptr=0;
  96.         continue;
  97.     }
  98.     if (inptr<iblen-1) {
  99.         b[inptr+blen]=b[inptr]=i;
  100.         ++inptr;
  101.     }
  102.     else {
  103.         b[inptr]=i;
  104.         if(++inptr==blen) inptr=0;
  105.     }
  106.     } while (--j);
  107.     swd_mlf=MINLEN-1;
  108. }
  109.  
  110. void swd_findbest(void) {
  111.  
  112.     register U16B i,ref,cnt,ptr,start_len;
  113.     register S16B c;
  114.     
  115.     i=HASH(bbf);
  116.     if ((cnt=ccnt[i]++)>MAXCNT) cnt=MAXCNT;
  117.     ptr=ll[bbf]=cr[i];
  118.     cr[i]=bbf;
  119.     swd_char=b[bbf];
  120.     if ((start_len=swd_mlf)>=bbl) {
  121.     if (bbl==0) swd_char=-1;
  122.     best[bbf]=30000;
  123.     }
  124.     else {
  125.     for (ref=b[bbf+swd_mlf-1];cnt--;ptr=ll[ptr]) {
  126.         if (b[ptr+swd_mlf-1]==ref && 
  127.         b[ptr]==b[bbf] && b[ptr+1]==b[bbf+1]) {
  128.         {
  129.             register unsigned char *p1=b+ptr+3,*p2=b+bbf+3;
  130.             for (i=3;i<bbl;++i) {
  131.             if (*p1++!=*p2++) break; 
  132.             }
  133.         }
  134.         if (i<=swd_mlf) continue;
  135.         swd_bpos=ptr;                
  136.         if ((swd_mlf=i)==bbl || best[ptr]<i) break;
  137.         ref=b[bbf+swd_mlf-1];
  138.         }
  139.     }
  140.     best[bbf]=swd_mlf;
  141.     if (swd_mlf>start_len) {
  142.         if (swd_bpos<bbf) swd_bpos=bbf-swd_bpos-1;
  143.         else swd_bpos=blen-1-swd_bpos+bbf;
  144.     }
  145.     }
  146.     if (binb==cblen) --ccnt[HASH(inptr)];
  147.     else ++binb;
  148.     if (++bbf==blen) bbf=0;
  149.     if ((c=getbyte())<0) {
  150.     --bbl;
  151.     if(++inptr==blen) inptr=0;
  152.     return;
  153.     }
  154.     if (inptr<iblen-1) {
  155.     b[inptr+blen]=b[inptr]=c;
  156.     ++inptr;
  157.     }
  158.     else {
  159.     b[inptr]=c;
  160.     if (++inptr==blen) inptr=0;
  161.     }
  162. }
  163.  
  164. #endif
  165.  
  166. void swd_dinit(U16B bufl) {
  167.  
  168.     cblen=bufl;
  169.     b=malloc(cblen*sizeof(unsigned char));    
  170.     if (b==NULL) {
  171.     swd_cleanup();
  172.     error(1,ERR_MEM,"swd_dinit()");
  173.     }
  174.     bbf=0;
  175. }
  176.  
  177.  
  178. void swd_dpair(U16B l, U16B p) {
  179.     
  180.     if (bbf>p) p=bbf-1-p;
  181.     else p=cblen-1-p+bbf;
  182.     while (l--) {
  183.     b[bbf]=b[p];
  184.     putbyte(b[p]);
  185.     if (++bbf==cblen) bbf=0;
  186.     if (++p==cblen) p=0;
  187.     }
  188. }
  189.  
  190. void swd_dchar(S16B c) {
  191.  
  192.     b[bbf]=c;
  193.     putbyte(c);
  194.     if (++bbf==cblen) bbf=0;
  195. }
  196.